package sword_offer;

import common.TreeNode;

import java.util.*;

/**
 * @ClassName _32_1_LevelOrderTree
 * @Description: 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 * @Author: yongliang.ma
 * @Create_time:2022/10/10 13:25
 */
public class _32_3_LevelOrderTree {

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        deque.offer(root);
        boolean fromLeft = true;
        int size = 0;
        while (!deque.isEmpty()){
            size = deque.size();
            List<Integer> list = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.poll();
                list.add(treeNode.val);
                if (treeNode.left != null)
                    deque.offer(treeNode.left);
                if (treeNode.right != null)
                    deque.offer(treeNode.right);
            }
            if (!fromLeft)
                Collections.reverse(list);
            // 反转该标志，下次倒排
            fromLeft = !fromLeft;
            result.add(list);
        }
        return result;
    }
}
